package com.jiang.剑指Offer.树.NC80;

import com.jiang.剑指Offer.树.TreeNode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author Jiang
 * @version 1.0
 * @date 2025/01/11 20:19
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param pRoot TreeNode类
     * @return int整型ArrayList<ArrayList <>>
     */
    // 队列
//     public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
//         ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 结果集合
//         if (pRoot == null) return res;
//
//         Queue<TreeNode> q = new LinkedList<>();
//         q.offer(pRoot); // 添加根节点
//         q.offer(null);  // 每一层结尾都会添加一个null，表示这行结束标志
//         ArrayList<Integer> row = new ArrayList<>(); // 每一层集合
//         while(!q.isEmpty()) {
//             TreeNode temp = q.poll();
//             if (temp == null) { // 到这层结尾
//                 res.add(row); // 将这层集合加入到结果集合中
//                 row = new ArrayList<>(); // 创建下一层集合
//                 if (!q.isEmpty()) q.offer(null); // 队列添加null， 表示下一层结束标志
//                 continue;
//             }
//             row.add(temp.val);
//             if (temp.left != null) q.add(temp.left);
//             if (temp.right != null) q.add(temp.right);
//         }
//         return res;
//     }

    // 递归
    public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<>(); // 结果集合
        // 树的层级从1开始递归计数
        recursion(pRoot, res, 1);
        return res;
    }

    private void recursion(TreeNode node, ArrayList<ArrayList<Integer>> res, int depth) {
        if (node != null) {
            // 数组长度小于当前层数，新开一层
            if (res.size() < depth) {
                res.add(new ArrayList<>());
            }
            // 数组从0开始计数因此减1，在节点当前层的数组中插入节点
            res.get(depth - 1).add(node.val);
            // 递归左右时节点深度记得加1
            recursion(node.left, res, depth + 1);
            recursion(node.right, res, depth + 1);
        }
    }
}
